package com.test.daily.leetcode.y2022.m06.day0618.v02;

import java.util.ArrayList;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/18 上午 10:45
 * @version: 1.0
 */
public class Solution {
    public static class Node {
        int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }

    public static boolean isContains(Node n1, Node n2) {
        // 1。 排除異常情況
        if (n1 == null && n2 != null) {
            return false;
        }
        if (n2 == null && n1 != null) {
            return false;
        }
        // 2. 判斷是不是相同的樹
        if (isSame(n1, n2)) {
            return false;
        }
        // 3. 判斷是不是子樹
        // 3.1 判断先序遍历
        String[] str1 = preStr(n1);
        String[] str2 = preStr(n2);
        // 3.2 两个字串先后KMP比较是否包含
        String[] small = str1.length < str2.length ? str1 : str2;
        String[] big = small == str1 ? str2 : str1;
        int index = isIndexOf(big, small);
        return index == -1 ? false: true;
    }

    public static int isIndexOf(String[] big, String[] small){
        int x = 0;
        int y = 0;
        int[] nexts = getNext(small);
        while(x < big.length && y < small.length){
            if(isEqual(big[x], small[y])){
                x++; y++;
            } else if(nexts[y] == -1){
                x++;
            } else {
                y = nexts[y];
            }
        }
        return y == small.length ? x - y: -1;
    }
    public static boolean isEqual(String a, String b){
        if(a == null && b == null){
            return true;
        }
        if( a == null && b != null || a != null && b == null){
            return false;
        }
        return a.equals(b);

    }

    public static int[] getNext(String[] str2) {
        if (str2.length < 1) {
            return new int[]{-1};
        }
        int[] nexts =  new int[str2.length];
        nexts[0] = -1;
        nexts[1] = 0;
        int i = 2;
        int cnt = 0;
        while( i < str2.length){
            if(str2[i] == str2[cnt]){
                nexts[i++] = ++cnt;
            } else if(cnt > 0){
                cnt = nexts[cnt];
            } else {
                nexts[i++] = 0;
            }
        }
        return nexts;
    }

    public static String[] preStr(Node n1) {
        ArrayList<String> n1List = new ArrayList<>();
        pre(n1, n1List);
        String[] str = new String[n1List.size()];
        for (int i = 0; i < str.length; i++) {
            str[i] = n1List.get(i);
        }
        return str;
    }

    public static void pre(Node head, ArrayList<String> list) {
        if (head == null) {
            list.add(null);
            return;
        }
        list.add(new String().valueOf(head.val));
        pre(head.left, list);
        pre(head.right, list);
    }

    public static boolean isSame(Node n1, Node n2) {
        if (n1 == null && n2 == null) {
            return true;
        }
        if (n1 == null && n2 != null || n1 != null && n2 == null) {
            return false;
        }
        if (n1.val == n2.val && isSame(n1.left, n2.left) && isSame(n1.right, n2.right)) {
            return true;
        }
        return false;
    }
}
